package test;

/**
 * Created by Caesar on 2015/11/26.
 */
public class MyLevenshtein {

    public static void main(String[] args) {
//要比较的两个字符串
        String str1 = "jack";
        String str2 = "jeck";
        System.out.println(Leven(str1, str2));
    }

    public static float Leven(String value1, String value2) {
        int len1 = value1.length();
        int len2 = value2.length();
        int[][] dif = new int[len1 + 1][len2 + 1];
        for (int a = 0; a <= len1; a++) {
            dif[a][0] = a;
        }
        for (int a = 0; a <= len2; a++) {
            dif[0][a] = a;
        }
        int temp = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (value1.indexOf(i - 1) == value2.indexOf(j - 1)) {
                    temp = 0;
                } else {
                    temp = 1;
                }
                dif[i][j] = Min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1,
                        dif[i - 1][j] + 1);
            }
        }

        float similarity = 1 - (float) dif[len1][len2] / Math.max(len1, len2);
        return similarity;
    }

    public static int Min(int a, int b, int c) {
        int i = a < b ? a : b;
        return i = i < c ? i : c;
    }
}
